/**
 * @file TestBinarySearchTree.cpp
 * @author Hu Yumeng (3210103435@zju.edu.cn)
 * @brief BinarySearchTree
 * @version 0.1
 * @date 2022-10-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <iostream>
#include <vector>
#include<ctime>
#include "BinarySearchTree.h"
using namespace std;

/**
 * @brief 数组_arr排序的函数声明
 * 
 * @tparam Comparable 
 * @param _arr 
 * @param _mode 
 */
template <typename Comparable>
void BSTSorting(std::vector<Comparable>& _arr,int _mode);
template <typename Comparable>
vector<Comparable> m_sort(std::vector<Comparable>& _arr);

/**
 * @brief 数组_arr乱序的函数声明
 * 
 * @tparam Comparable 
 * @param _arr 
 * @return vector<Comparable> 
 */
template <typename Comparable>
 vector<Comparable> RandomVector(std::vector<Comparable>& _arr);


// Test program
int main()
{
    BinarySearchTree<int> t;
    int NUMS = 20;
    const int GAP = 3711;
    int i;

    cout << "Checking... (no more output means success)" << endl;

    /**
     * @brief 在 t 中插入元素
     * 
     */
    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);
    
    /**
     * @brief 剔除 t 中的奇数元素
     * 
     */
    for (i = 1; i < NUMS; i += 2)
        t.remove(i);

    /// 排序输出小于40的元素
    if (NUMS < 40)
        t.printTree();
    /// 测试函数findmin()和findmax()
    if (t.findMin() != 2 || t.findMax() != std::max(NUMS - 2,GAP))
        cout << "FindMin or FindMax error!" << endl;
    
    /// 测试函数contains()
    for (i = 2; i < NUMS; i += 2)
        if (!t.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2)
    {
        if (t.contains(i))
            cout << "Find error2!" << endl;
    }

    /// 测试重载运算符 =
    BinarySearchTree<int> t2;
    t2 = t;

    for (i = 2; i < NUMS; i += 2)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2)
    {
        if (t2.contains(i))
            cout << "Find error2!" << endl;
    }

    cout << "Finished testing" << endl;

    /**
     * @brief 构造数组obj
     * 
     */
    vector<int>obj;
    for (i = 10; i >0; i--)
    {
        obj.push_back(i);
    }
    
    for(i=1;i<=10;i++)
    {
    clock_t starttime = clock();
    BSTSorting(obj, 1);           ///_mode = 0时的测试
    clock_t endtime = clock();

    cout<<"_mode = 1效率用时:"<<double(endtime - starttime)/CLOCKS_PER_SEC<<"s"<<endl;
    }

    // BSTSorting(obj, 1);           ///_mode = 1时的测试
    return 0;
}

/**
 * @brief BSTSorting函数实现
 * 
 * @tparam Comparable 
 * @param _arr 
 * @param _mode 
 */
template <typename Comparable>
void BSTSorting(std::vector<Comparable>& _arr,int _mode )
{
    int j;
    BinarySearchTree<Comparable> m;     ///定义对象m

    if (_mode == 0)    
    {
        /// @brief _mode = 0时
        /// @tparam Comparable 
        /// @param _arr 
        /// @param _mode 
        for (j = 0; j < _arr.size(); j++)
        {
            m.insert(_arr[j]);
        }
        m.printTree();       ///直接输出数组
    }
    else {
        /// @brief _mode = 1时
        /// @tparam Comparable 
        /// @param _arr 
        /// @param _mode 
        _arr = RandomVector(_arr);       ///调用RandomVector将数组乱序
       
        for (j = 0; j < _arr.size(); j++)
        {
             cout << _arr[j] << endl;            ///输出乱序数组
        } 
        
        for (j = 0; j < _arr.size(); j++)
        {
             m.insert(_arr[j]);                         
        }
          m.printTree();                                  ///排序后输出
    }
};

/**
 * @brief RandomVector乱序函数实现
 * 
 * @tparam Comparable 
 * @param _arr 
 * @return vector<Comparable> 
 */
template <typename Comparable>
vector<Comparable> RandomVector(std::vector<Comparable>& _arr)
{
    std::vector<Comparable> new_arr;        ///生成新数组
    int i;
    for (i = _arr.size(); i > 0; i--)
    {
        srand(unsigned(time(NULL)));
        /// index记录选中的随机下标
        int index = rand() % i;
        /// 将选中下标对应的元素push到新数组
        new_arr.push_back(_arr[index]);
        /// 将原数组中选中的元素剔除
        _arr.erase(_arr.begin() + index);
    }
    
    /// 返回新数组
    return new_arr;
};